package com.arron.algorithm.leetcodetop100.双指针.n数之和;


import java.util.*;

/**
 *  Leetcode 15. 三数之和
 */
public class 三数之和 {


    public static void main(String[] args) {

        int[] a = {-1,0,1,2,-1,-4};

        System.out.println(threeSum2(a));
    }


    /**
     * 暴力解法
     * 时间复杂度 ： O（N3） 空间复杂度为O（1）
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> res = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                for (int k = j+1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        res.add(Arrays.asList(nums[i],nums[j],nums[k]));
                    }
                }
            }
        }
        return new ArrayList<>(res);
    }


    /**
     * 排序+双指针
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSum2(int[] nums) {

        List<List<Integer>> res = new ArrayList<>();
        //判断特殊情况
        if (nums ==null ||nums.length<3){
            return res;
        }
        //先对数组排序
        Arrays.sort(nums);
        for (int i = 0; i < nums.length-2; i++) {

            int sum = 0;
            int r =nums.length-1;
            int l = i+1;

            if(nums[i]>0){
                continue;
            }
            if(i>0 && nums[i] == nums[i-1]){
                continue;
            }

            while (l<r){
                sum = nums[i]+nums[r]+nums[l];
                if (sum == 0){
                    List<Integer> tempList = new ArrayList<>();
                    tempList.add(nums[i]);
                    tempList.add(nums[r]);
                    tempList.add(nums[l]);
                    res.add(tempList);

                    //去除重复的
                    while (l<r && nums[l] == nums[l+1]) l++;
                    while (l<r && nums[r] == nums[r-1]) r--;
                    l++;
                    r--;
                }else if (sum<0){
                    //小于0
                    l++;

                }else {
                    //大于0
                    r--;
                }
            }
        }
        return res;
    }


}
